import math
from typing import Union, overload
from time import perf_counter

# 常量定义
sqrt2 = math.sqrt(2)


class Vector2:
    '''二维浮点向量类, 支持基本向量运算'''

    def __init__(self, x: Union[int, float] = 0, y: Union[int, float] = 0) -> None:
        '''初始化二维向量'''
        self.x = x
        self.y = y

    def copy(self) -> 'Vector2':
        '''创建向量的浅拷贝'''
        return Vector2(self.x, self.y)

    @staticmethod
    def chebyshev_distance(v1: 'Vector2', v2: 'Vector2') -> float:
        '''
        计算切比雪夫距离
        '''
        dx = abs(v1.x - v2.x)
        dy = abs(v1.y - v2.y)
        return dx + dy - min(dx, dy) * (2 - sqrt2)

    @staticmethod
    def manhattan_distance(v1: 'Vector2', v2: 'Vector2') -> float:
        '''计算曼哈顿距离'''
        return abs(v1.x - v2.x) + abs(v1.y - v2.y)

    @staticmethod
    def euclidean_distance(v1: 'Vector2', v2: 'Vector2') -> float:
        '''计算欧几里得距离'''
        return math.sqrt((v1.x - v2.x)**2 + (v1.y - v2.y)**2)

    @staticmethod
    def euclidean_distance_2(v1: 'Vector2', v2: 'Vector2') -> float:
        '''计算欧几里得距离的平方'''
        return (v1.x - v2.x)**2 + (v1.y - v2.y)**2

    @staticmethod
    def octile_distance(v1: 'Vector2', v2: 'Vector2') -> float:
        '''计算 Octile 距离, 对角线为 sqrt2, 直线为 1'''
        dx = abs(v1.x - v2.x)
        dy = abs(v1.y - v2.y)
        return min(dx, dy) * sqrt2 + abs(dx - dy)

    def __repr__(self) -> str:
        '''返回向量的字符串表示'''
        return f"({self.x}, {self.y})"

    def __add__(self, other: Union['Vector2', 'Vector2Int']) -> 'Vector2':
        '''向量加法'''
        return Vector2(self.x + other.x, self.y + other.y)

    def __sub__(self, other: Union['Vector2', 'Vector2Int']) -> 'Vector2':
        '''向量减法'''
        return Vector2(self.x - other.x, self.y - other.y)

    def dot(self, other: Union['Vector2', 'Vector2Int']) -> float:
        '''计算点积'''
        return self.x * other.x + self.y * other.y

    def __eq__(self, other: Union['Vector2', 'Vector2Int']) -> bool:
        '''判断向量相等 (精度 1e-6)'''
        return abs(self.x - other.x) < 1e-6 and abs(self.y - other.y) < 1e-6

    def __mul__(self, other: Union[int, float]) -> 'Vector2':
        '''向量与标量相乘'''
        return Vector2(self.x * other, self.y * other)

    def __rmul__(self, other: Union[int, float]) -> 'Vector2':
        '''标量与向量相乘'''
        return Vector2(self.x * other, self.y * other)

    def __truediv__(self, other: Union[int, float]) -> 'Vector2':
        '''向量与标量相除'''
        if other == 0:
            raise ZeroDivisionError("不能除以零")
        return Vector2(self.x / other, self.y / other)

    def __floordiv__(self, other: Union[int, float]) -> 'Vector2':
        '''向量与标量整除'''
        if other == 0:
            raise ZeroDivisionError("不能除以零")
        return Vector2(self.x // other, self.y // other)

    def __hash__(self):
        '''计算哈希值'''
        return hash((self.x, self.y))

    def to_vector2_int(self) -> 'Vector2Int':
        '''四舍五入转换为整数向量'''
        return Vector2Int(round(self.x), round(self.y))


class Vector2Int:
    '''二维整数向量类, 支持基本向量运算'''

    def __init__(self, x: int = 0, y: int = 0) -> None:
        '''初始化整数向量'''
        self.x = x
        self.y = y

    def copy(self) -> 'Vector2Int':
        '''创建向量的浅拷贝'''
        return Vector2Int(self.x, self.y)

    @staticmethod
    def chebyshev_distance(v1: 'Vector2Int', v2: 'Vector2Int') -> int:
        '''计算切比雪夫距离'''
        dx = abs(v1.x - v2.x)
        dy = abs(v1.y - v2.y)
        return max(dx, dy)

    @staticmethod
    def manhattan_distance(v1: 'Vector2Int', v2: 'Vector2Int') -> int:
        '''计算曼哈顿距离'''
        return abs(v1.x - v2.x) + abs(v1.y - v2.y)

    @staticmethod
    def euclidean_distance(v1: 'Vector2Int', v2: 'Vector2Int') -> float:
        '''计算欧几里得距离'''
        return math.sqrt((v1.x - v2.x)**2 + (v1.y - v2.y)**2)

    @staticmethod
    def euclidean_distance_2(v1: 'Vector2Int', v2: 'Vector2Int') -> int:
        '''计算欧几里得距离的平方'''
        return (v1.x - v2.x)**2 + (v1.y - v2.y)**2

    @staticmethod
    def octile_distance(v1: 'Vector2Int', v2: 'Vector2Int') -> float:
        '''计算 Octile 距离, 对角线为 sqrt2, 直线为 1'''
        dx = abs(v1.x - v2.x)
        dy = abs(v1.y - v2.y)
        return min(dx, dy) * sqrt2 + abs(dx - dy)

    def __repr__(self) -> str:
        '''返回向量的字符串表示'''
        return f"({self.x}, {self.y})"

    @overload
    def __add__(self, other: 'Vector2Int') -> 'Vector2Int':
        '''向量加法'''

    @overload
    def __add__(self, other: 'Vector2') -> 'Vector2':
        '''向量加法'''

    def __add__(self, other: Union['Vector2Int', 'Vector2']) -> Union['Vector2Int', 'Vector2']:
        '''向量加法'''
        if isinstance(other, Vector2):
            return Vector2(self.x + other.x, self.y + other.y)
        return Vector2Int(self.x + other.x, self.y + other.y)

    @overload
    def __sub__(self, other: 'Vector2Int') -> 'Vector2Int':
        '''向量减法'''

    @overload
    def __sub__(self, other: 'Vector2') -> 'Vector2':
        '''向量减法'''

    def __sub__(self, other: Union['Vector2Int', 'Vector2']) -> Union['Vector2Int', 'Vector2']:
        '''向量减法'''
        if isinstance(other, Vector2):
            return Vector2(self.x - other.x, self.y - other.y)
        return Vector2Int(self.x - other.x, self.y - other.y)

    def dot(self, other: Union['Vector2Int', 'Vector2']) -> float:
        '''计算点积'''
        return self.x * other.x + self.y * other.y

    def __eq__(self, other: Union['Vector2Int', 'Vector2']) -> bool:
        '''判断向量相等'''
        if isinstance(other, Vector2):
            return abs(self.x - other.x) < 1e-6 and abs(self.y - other.y) < 1e-6
        return self.x == other.x and self.y == other.y

    @overload
    def __mul__(self, other: int) -> 'Vector2Int':
        '''向量与标量相乘'''

    @overload
    def __mul__(self, other: float) -> 'Vector2':
        '''向量与标量相乘'''

    def __mul__(self, other: Union[int, float]) -> Union['Vector2Int', 'Vector2']:
        '''向量与标量相乘'''
        if isinstance(other, float):
            return Vector2(self.x * other, self.y * other)
        return Vector2Int(self.x * other, self.y * other)

    @overload
    def __rmul__(self, other: int) -> 'Vector2Int':
        '''标量与向量相乘'''

    @overload
    def __rmul__(self, other: float) -> 'Vector2':
        '''标量与向量相乘'''

    def __rmul__(self, other: Union[int, float]) -> Union['Vector2Int', 'Vector2']:
        '''标量与向量相乘'''
        if isinstance(other, float):
            return Vector2(self.x * other, self.y * other)
        return Vector2Int(self.x * other, self.y * other)

    def __truediv__(self, other: Union[int, float]) -> 'Vector2':
        '''向量与标量相除'''
        if other == 0:
            raise ZeroDivisionError("不能除以零")
        return Vector2(self.x / other, self.y / other)

    def __floordiv__(self, other: Union[int, float]) -> Union['Vector2Int', 'Vector2']:
        '''向量与标量整除'''
        if other == 0:
            raise ZeroDivisionError("不能除以零")
        if isinstance(other, float):
            return Vector2(self.x // other, self.y // other)
        return Vector2Int(self.x // other, self.y // other)

    def __hash__(self):
        '''计算哈希值'''
        return hash((self.x, self.y))

    def to_vector2(self) -> 'Vector2':
        '''转换为浮点向量'''
        return Vector2(float(self.x), float(self.y))


def point_2_line(p: Vector2, a1: Vector2, a2: Vector2) -> float:
    '''
    计算点到直线的距离
    Args:
        p: 直线外的点
        a1: 直线上的点
        a2: 直线上的点
    Returns:
        float: 点 p 到直线 ab 的距离
    '''
    numerator = abs((a2.x - a1.x) * (a1.y - p.y) - (a1.x - p.x) * (a2.y - a1.y))
    denominator = Vector2.euclidean_distance(a1, a2)
    if denominator < 1e-9:
        return Vector2.euclidean_distance(p, a1)
    return numerator / denominator


def line_with_circle(center: Vector2, radius: float, p1: Vector2, p2: Vector2, segment: bool = False) -> bool:
    '''
    判断直线/线段与圆是否相交
    Args:
        center: 圆心坐标
        radius: 圆的半径
        p1: 直线/线段的第一个点
        p2: 直线/线段的第二个点
        segment: 如果为 True, 则判断线段; 否则判断直线. Defaults to False.
    Returns:
        bool: 如果相交则返回 True, 否则返回 False
    '''
    # 检查圆心到直线的距离
    dist_to_line = point_2_line(center, p1, p2)
    if dist_to_line > radius:
        return False

    # 如果是直线, 此时必定相交
    if not segment:
        return True

    # 检查线段端点是否在圆内
    if Vector2.euclidean_distance_2(center, p1) < radius**2 or Vector2.euclidean_distance_2(center, p2) < radius**2:
        return True

    # 检查垂足是否在线段上
    dot1 = (p2 - p1).dot(center - p1)
    dot2 = (p1 - p2).dot(center - p2)
    if dot1 > 0 and dot2 > 0:
        return True

    return False


def line_with_triangle(t1: Vector2, t2: Vector2, t3: Vector2, p1: Vector2, p2: Vector2, segment: bool = False) -> bool:
    '''
    判断直线/线段与三角形是否相交, 通过检查与三角形各边的相交情况
    Args:
        t1: 三角形的顶点
        t2: 三角形的顶点
        t3: 三角形的顶点
        p1: 直线/线段的点
        p2: 直线/线段的点
        segment (bool, optional): 如果为 True, 则判断 p1-p2 是否为线段
    Returns:
        bool: 如果相交则返回 True, 否则返回 False
    '''
    triangle_edges = [(t1, t2), (t2, t3), (t3, t1)]
    for edge_start, edge_end in triangle_edges:
        if line_with_line(p1, p2, edge_start, edge_end, segment1=segment, segment2=True):
            return True
    return False


def line_with_line(a1: Vector2, a2: Vector2, b1: Vector2, b2: Vector2, segment1=False, segment2=False) -> bool:
    '''
    判断两条直线或线段是否相交
    Args:
        a1: 第一条直线/线段的点
        a2: 第一条直线/线段的点
        b1: 第二条直线/线段的点
        b2: 第二条直线/线段的点
        segment1 (bool, optional): 如果为 True, 则 a1-a2 为线段
        segment2 (bool, optional): 如果为 True, 则 b1-b2 为线段
    Returns:
        bool: 如果相交则返回 True, 否则返回 False
    '''
    da = a2 - a1
    db = b2 - b1

    # 计算叉积分母
    denominator = da.x * db.y - da.y * db.x

    # 如果分母为0, 说明两条线平行或共线
    if abs(denominator) < 1e-9:
        return False

    dp = b1 - a1
    # 计算参数 t 和 u
    t = (dp.x * db.y - dp.y * db.x) / denominator
    u = (dp.x * da.y - dp.y * da.x) / denominator

    # 如果是判断直线, 只要不平行就一定相交
    if not segment1 and not segment2:
        return True

    # 如果是判断线段, t 和 u 必须都在 [0, 1] 区间内
    intersect = True
    if segment1 and not (0 <= t <= 1):
        intersect = False
    if segment2 and not (0 <= u <= 1):
        intersect = False

    return intersect


def point_on_segment(p: Vector2, a1: Vector2, a2: Vector2) -> bool:
    '''
    判断点是否在线段上
    Args:
        p: 需要判断的点
        a1: 线段的端点
        a2: 线段的端点
    Returns:
        bool: 如果点在线段上则返回 True, 否则返回 False
    '''
    # 检查共线性（通过叉积是否为0）
    cross_product = (p.y - a1.y) * (a2.x - a1.x) - (p.x - a1.x) * (a2.y - a1.y)
    if abs(cross_product) > 1e-9:
        return False

    # 检查点是否在线段的边界框内
    dot_product = (p.x - a1.x) * (a2.x - a1.x) + (p.y - a1.y) * (a2.y - a1.y)
    if dot_product < 0:
        return False

    squared_length_b = (a2.x - a1.x)**2 + (a2.y - a1.y)**2
    if dot_product > squared_length_b:
        return False

    return True


def timed(func):
    '''计时函数'''
    start = perf_counter()
    result = func()
    return result, perf_counter() - start


if __name__ == '__main__':
    # 向量操作测试
    v1 = Vector2(1, 2)
    v2 = Vector2(2, 5)
    v3 = v1.copy()
    print(f'{v1 = }')
    print(f'{v2 = }')
    print(f'{v3 = }')
    print(f'{v1 + v2 = }')
    print(f'{v1 - v2 = }')
    print(f'{v1 == v2 = }')
    print(f'{v1 == v3 = }')
    print(f'Chebyshev distance: {Vector2.chebyshev_distance(v1, v2):.4f}')
    print(f'Euclidean distance: {Vector2.euclidean_distance(v1, v2):.4f}')
    print(f'Euclidean distance squared: {Vector2.euclidean_distance_2(v1, v2):.4f}')

    # 点到直线距离测试
    p = Vector2(3, 3)
    a = Vector2(0, 0)
    b = Vector2(5, 5)
    dist = point_2_line(p, a, b)
    print(f'Distance from point {p} to line segment {a}-{b}: {dist:.4f}')

    # 线与圆碰撞测试
    center = Vector2(0, 0)
    radius = 2
    p1 = Vector2(-3, 0)
    p2 = Vector2(3, 0)
    print(f'Line intersects circle: {line_with_circle(center, radius, p1, p2)}')

    # 线段与圆碰撞测试
    p1_seg = Vector2(-3, 0)
    p2_seg = Vector2(-2.1, 0)
    print(f'Segment intersects circle: {line_with_circle(center, radius, p1_seg, p2_seg, segment=True)}')

    # 线与线碰撞测试
    a1 = Vector2(0, 0)
    a2 = Vector2(3, 3)
    b1 = Vector2(0, 3)
    b2 = Vector2(3, 0)
    print(f'Lines intersect: {line_with_line(a1, a2, b1, b2)}')

    # 线段与线段不相交测试
    a1 = Vector2(0, 0)
    a2 = Vector2(1, 1)
    b1 = Vector2(2, 2)
    b2 = Vector2(3, 3)
    print(f'Segments intersect: {line_with_line(a1, a2, b1, b2, segment1=True, segment2=True)}')

    # 点是否在线段上测试
    p_on_seg = Vector2(1, 1)
    seg_a = Vector2(0, 0)
    seg_b = Vector2(2, 2)
    print(f'Point {p_on_seg} on segment {seg_a}-{seg_b}: {point_on_segment(p_on_seg, seg_a, seg_b)}')

    # 三角形与线段碰撞测试
    t1 = Vector2(0, 0)
    t2 = Vector2(2, 0)
    t3 = Vector2(1, 2)
    line_p1 = Vector2(1, 1)
    line_p2 = Vector2(3, 3)
    print(f'Line intersects triangle: {line_with_triangle(t1, t2, t3, line_p1, line_p2, segment=True)}')
    line_p3 = Vector2(3, 3)
    line_p4 = Vector2(4, 4)
    print(f'Line intersects triangle: {line_with_triangle(t1, t2, t3, line_p3, line_p4, segment=True)}')
